"""
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

考虑后面最后一步 可以一步走到 也可以两步直接跨过
fn = fn-1 + fn-2
递推公式
"""
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        stack = [1, 2]
        i = 2
        while i < n:
            stack.append(stack[i-1]+stack[i-2])
            i += 1
        return stack[n-1]

s = Solution()
print(s.climbStairs(5))